COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\rm
C00011 ENDMK
C⊗;
\rm
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}

\line{\sevenrm 162B04.tex[1,RWF] \today\hfill}

\centerline{The Hull-Finding Algorithm H}
\centerline{by R.W.~Floyd}

\vskip 3.5in

Given originally a finite set $S$ of points in a convex region $R$, we are finding
its convex hull.  At a certain time, we have found that points $P↓1,\ldots ,P↓k$ in
order are vertices of the hull.  A region called $INT$ is the interior of the
convex closure $POL$ of $\{ P↓i$, $1≤i≤k\}$; $S↓{INT}=S\bigcap INT$, the points of
$S$ in $INT$, can be ignored as not affecting the hull.  There is a region called
$OPEN$, separated from $INT$ by $L=P↓1P↓k$, such that $S\subset OPEN\bigcup POL$,
and $OPEN\bigcup POL$ is convex; the complementary region of $R$, $EXT$, then
contains no points of $S$ and no part of the convex hull.  We use $S↓{OPEN}$ to
mean $S\bigcap OPEN$.  Ordinarily the boundaries $L↓A$ and $L↓B$ between $OPEN$
and $EXT$ are straight lines.  
$S=S↓{OPEN}\bigcup\{ P↓1,\ldots ,P↓k\}\bigcup S↓{INT}$.

We now identify the point $P↓{k+1}$ of $S↓{OPEN}$ which makes the smallest angle
$P↓{k+1}P↓kL↓B$.  No points of $S$ lie to the right of $L↓C$, so the region
$CP↓kB$ is deleted from $OPEN$, and added to $EXT$.  Similarly, the interior of
$\Delta P↓1P↓kP↓{k+1}$ is deleted from $OPEN$ and added to $INT$; points of
$S$ in this triangle are moved from $S↓{OPEN}$ to $S↓{INT}$, and $P↓{k+1}$ is
removed from $S↓{OPEN}$.  We now replace $L$ by $P↓1P↓{k+1}$, replace $L↓B$
by $L↓C$, increase $k$ by $1$, and repeat the process.

The process stops when $S↓{OPEN}$ is empty.  At that point, $P↓1\ldots P↓k$
is the (ordered) convex hull of $S$.

The process is initialized by finding (say) the lowest point of $S$ as $P↓1$.
$L$ is the horizontal line through $P↓1$; $EXT$ is the region below $L$,
$INT$ is empty, $OPEN$ is the region above $L$, $S↓{OPEN}=S-\{ P↓1\}$, 
$S↓{INT}=0$, $L↓A=AP↓1$, $L↓B=P↓1B$, $k=1$.

\vskip 1.75in

Alternative initialization:  From an arbitrary point $A$ on boundary of $R$,
find $P↓1$, the point of $S$ which minimizes the angle $TAP↓1$, where $AT$ is 
tangent to $R$.  Proceed as before.

\vskip 2.5in

The above algorithm $H$ is inefficient when we are given a concrete set $S$.
It has two merits, however.

(1) By analyzing $H$, we can determine the expected number of points on the
hull, the expected area of the hull, and other statistics.

(2) We can do Monte Carlo experiments using $H$, assuming statistical properties
of $S$, and only generating the points of $S$ which, as successive values of
$P↓k$, actually fall on the hull.  The expected number processed is then at most
$O(|S|↑{1/3})$.

\vskip 2.5in

Assume first that $S$ is given only by a density distribution $\rho (x,y)=
\rho (\overline z)$.  (An important special case:  $\rho (x,y)≡1$).

The probability that no point of $S$ lies in the region $Q$, above, is
$exp(-\int↓Q\rho (z)dz)$.  We can choose the line $L↓C$ randomly with this
property by choosing a random number $r$ uniformly over $(0,1)$.  We then
locate $L↓C$ so that $\int↓Q\rho (z)dz=-\ln r$.  If $\int↓{S↓{OPEN}}\rho (z) dz
<-\ln r$, we assume $S↓{OPEN}=0$.  (Special case:  area of $Q<-\ln r$.)  To locate
$P↓{k+1}$ on $L↓C$, we want to use a distribution which is proportional both
to the local value of $\rho$, and to the distance $|zP↓k|$ from $P↓k$.  Choose
another random number $r↑{\prime}$, and select $P↓{k+1}$ such that
$$\eqalign{\int↑{P↓{k+1}}↓{{P}↓k}\rho (z)|zP↓k|zd&=r↑{\prime}\int↑C↓{P↓k}\rho
(z)|zP↓k|dz.\cr
\hbox{(Special case; let}|P↓kP↓{k+1}|&=\sqrt{r↑{\prime}}|P↓kC|.)\cr}$$

Alternatively, we may be given $S$ by the property that it contains a certain
particular number $n$ of points, and that the distribution density
$\rho (x,y)=\rho (\overline z)$, governs, for each point, the relative probability
of its being at $\overline z$.  
Assume that $m$ is the number of points in $S↓{OPEN}\bigcup S↓{INT}$, i.e.,
$n-k$.  Assume that $I$ is $\int ↓{OPEN\bigcup INT}\rho (\overline z)d\overline z$.
The only difference in the algorithm (except for an analogous difference in the
initialization), is that instead of equating $\int ↓Q\rho (z)dz$ to $-\ln r$,
we equate ${\int ↓Q\rho (z)dz\over I}$ to $1-r↑{1/m}$.  (Special case: area of
$Q=I(1-r↑{1/m})$.)  If $\int ↓{OPEN}<I(1-r↑{1/m})$, or if $m=0$, we assume
$S↓{OPEN}=0$, and stop.  Note that when we add to $EXT$, we must
correspondingly diminish $I$.

\vfil\eject

A special case where it is possible to compute the expected number of points on
the hull arises when points are distributed with uniform density, say $1$,
and $OPEN$ is a triangle of area $A$.  Let $f(A)$ be the expected number of
hull points in $S↓{OPEN}$.  The distribution of the area $Q$ added to $EXT$
in the first step is $e↑{-Q}$, $0≤Q≤A$.  The fraction $\alpha$ of the remaining
area (if any) which remains in $OPEN$ is distributed triangularly, as
$2(1-\alpha)$.  Thus
$$f(A)=\int↑A↓{Q=0}e↑{-Q}\left[ 1+\int↑1↓{\alpha =0}2(1-\alpha)f(\alpha\cdot
(A-Q))d\alpha\right] dQ$$.
This may be integrated, giving ${2\over 3}\ln A+0(1)$.
\vfil\end